'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 15:06:05
LastEditTime: 2025-09-08 15:30:11
'''


class Solution:
    
    def longestPalindrome(self, s):

        dp = [[False] * len(s) for _ in range(len(s))]

        palindrome_len = 0
        palindrome_str = ""

        # 因为时对称矩阵
        for i in range(len(s) - 1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    # 单个字符的情况
                    if i == j:
                        dp[i][j] = True

                    elif j == i + 1:
                        dp[i][j] = True
                    # 状态转移方程
                    elif dp[i + 1][j - 1]:
                        dp[i][j] = True
                
                if dp[i][j] and j - i + 1 > palindrome_len:
                    palindrome_len = j - i + 1
                    palindrome_str = s[i: j+1]

        return palindrome_str
    

if __name__ == "__main__":

    s = "babad"
    sol = Solution()
    res = sol.longestPalindrome(s)

    print(res)



